import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
import java.util.*;

class Printer {
    public int[] clockwisePrint(int[][] mat, int n, int m) {
        // write code here
        //左上角
        int x1 = 0;
        int y1 = 0;
        //右下角
        int x2 = n-1;
        int y2 = m-1;
        int[] array = new int[n*m];
        int idx = 0;
        while(x1 <= x2 && y1 <= y2){
            //第一行x1,y1-y2
            for (int i = y1; i <= y2; i++){
                array[idx++] = mat[x1][i];
            }
            //最后一列x1+1-x2,y2
            for (int i = x1+1; i <= x2; i++){
                array[idx++] = mat[i][y2];
            }
            //最后一行x2,y2-1
            if (x1 < x2){
                for (int i = y2-1; i >= y1; i--){
                    array[idx++] = mat[x2][i];
                }
            }
            //第一列
            if (y1 < y2){
                for (int i = x2-1; i > x1; i--){
                    array[idx++] = mat[i][y1];
                }
            }
            x1++;
            y1++;
            x2--;
            y2--;


        }
        return array;
    }
}
class TreeNode {
      int val;
      javax.swing.tree.TreeNode left;
     javax.swing.tree.TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, javax.swing.tree.TreeNode left, javax.swing.tree.TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Test {
    private int maxW = 1;
    public int widthOfBinaryTree(javax.swing.tree.TreeNode root) {
        if(root == null){
            return 0 ;
        }
        Queue<javax.swing.tree.TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> indexList = new LinkedList<>();
        queue.add(root);
        indexList.add(1);
        int size = 1;
        while(!queue.isEmpty()){
            javax.swing.tree.TreeNode node = queue.poll();
            size--;
            int index = indexList.removeFirst();
            if (node.left != null){
                queue.add(node.left);
                indexList.add(2*index);
            }
            if(node.right != null){
                queue.add(node.right);
                indexList.add(2*index+1);
            }
            if (size == 0){
                if (indexList.size() >= 2){
                    maxW = Math.max(maxW,indexList.getLast() - indexList.getFirst() + 1);
                }
                size = queue.size();
            }


        }
        return maxW;

    }


}
